// a new bug in initialization a domain:
// dp[0].pre should be the last value
// 10 Apr

#include "backtracking.h"
#include <fstream>



BT::BT(int n1, int d1, int e1, int T, int *S):
  AC_CLASS(n1, d1, e1, T, S){
  //cerr << "Constructor: Backtracking begin" << endl;
  initBT();
  //cerr << "Constructor: Backtracking end" << endl;
}

BT::BT(int n1, int d1): AC_CLASS(n1, d1){
  initBT();
}

BT::BT(const char* filename) : AC_CLASS(filename){
  initBT();
}

void BT::initBT(){
	//cout << "Initializing Backtracker" << endl;
  valueOfVars = new int [n]; 
  for(int i=0; i<n; i++) { valueOfVars[i] = -1; }
  assignedVars = new int [n];
#ifdef VAL_COMPUTE
  currRankS=new double [n*d];  //used in Var/Val rankings
  nextRankS=new double [n*d];
  currRankC=new double [n*d];
  nextRankC=new double [n*d];
#endif
#ifdef DOMAIN_SPLIT
  domainSet= new int[n];  //used in domain splitting setups
  maxDomSegs=new int[n];
  domainSplitting=false;
#endif
#ifdef EXTENDED_STATISTICS
  backtrack_levels=new int[n];
  for(int i=0;i<n;i++) {backtrack_levels[i]=0;}
  deepest_backtrack=0;
#endif
 
  numOfFailedAssignments = 0;
  maxSuccessfulPhase = 0; 
  numOfBacktracks=0; 
  numPruned=0;
  lastPhase=-1;
  hasRanked=false;
}

BT::~BT(){
  //cerr << "Destructor: Backtracking begin" << endl;
  if (valueOfVars != NULL) delete [] valueOfVars;
  if (assignedVars != NULL) delete [] assignedVars;
#ifdef VAL_COMPUTE
  if (currRankS != NULL) delete [] currRankS;
  if (nextRankS != NULL) delete [] nextRankS;
  if (currRankC != NULL) delete [] currRankC;
  if (nextRankC != NULL) delete [] nextRankC;
#endif
#ifdef DOMAIN_SPLIT
  if(domainSet != NULL) delete [] domainSet;
  if(maxDomSegs !=NULL) delete [] maxDomSegs;
#endif
#ifdef EXTENDED_STATISTICS
  if(backtrack_levels != NULL) delete [] backtrack_levels;
#endif
  //cerr << "Destructor: Backtracking end" << endl;
}

bool BT::solve(){

  int dummyValue; // the value preceeds every value 

  // if phase starts as 0, it will make restoreDomain to recover
  // all those removed value in preprocessing, which would
  // cause problem for the control structure of MAC.
  // e.g. we may not establish support for a removed value var.value,
  // so if we restore the value var.value, its support is not well
  // defined.
  phase = -1; 
  dummyValue = headOfDomain(); // The head of the current domain 
  curValue = dummyValue;
  setPhase(phase);
  
  satisfiable = false;
  bool consistent=false;

  debugFlag = false;
  //cout << "Starting Solver" << endl;
  // initialize MAC and preprocess the csp (thats making it arc consistent)
  if( AC()) { // the csp is made arc consistent
    curVar = 0;
    phase = 0; 
    setPhase(phase);

    while ( phase < n && phase!=-2) { //-2 is the error value for this system

      // when the number of checks is huge ...
      if (num_cchecks > ONEMILLION) {
        num_cchecks_M += num_cchecks/ONEMILLION;
	num_cchecks = num_cchecks % ONEMILLION;
      }
      if (num_dchecks > ONEMILLION) {
        num_dchecks_M += num_dchecks/ONEMILLION;
	num_dchecks = num_dchecks % ONEMILLION;
      }

      // for k-residue
      if (num_ochecks > ONEMILLION) {
        num_ochecks_M += num_ochecks/ONEMILLION;
	num_ochecks = num_ochecks % ONEMILLION;
      }
      
	  //if(numOfFailedAssignments%1000==0)
      //std::cout << "[solv()] failed assignment " << numOfFailedAssignments << '\n'; 
      // for observing the progress of the search procedure


      //printSystem();
	  //cout << "Selecting Var/Value" << endl;
	  //cout << endl << endl;
      VR(curVar,curValue); //Combined Variable/Value selection
	  
	  //cout << "Selected Var, Val: " << curVar << "," << curValue << " at phase " << phase << endl;
	  //printCurrSupCon(curVar,curValue);
	  //printDomain(curVar);
	  //cout << vars[curVar].domainSize << endl;
	  //getchar();
//UGLY CODE: the domainsplitting code uses several spliced IFDEF clauses to add in the correct code.
//This makes it incredibly difficult to look at code in sections, however.
#ifdef DOMAIN_SPLIT 
	  if(curValue!=-1)
	  {
#endif
		assignVar(curVar, curValue);
		
		if (MAC(curVar, curValue)) { // csp is arc consistent
			//cout << "Arc Consistent Assignment at phase " << phase << endl;
			adjustDegree(curVar,true); //NEW FOR DEGREE
			assignedVars[phase] = curVar; // backup the current variable
			phase++; // move to the assignment of the next variable
			curValue = headOfDomain(); // set the value
			//moved this line into the consistent assignment block.  This is the only
			//position in the code where phase increases, so it should do best here.
			if(maxSuccessfulPhase < phase) maxSuccessfulPhase = phase; 
			//printSystem();

			setPhase(phase);
		}
		else {
			//cout << "Arc Inconsistent Assignment at phase "<< phase << endl;
			restoreDomains(phase); 
			RESTORE_MAC(phase); 
			numOfFailedAssignments++;
			restoreVars(curVar);
			//printSystem();
			//UGLY CODE.  This is done because this value is effectively arc inconsistent
			//due to a previous assignment.  Since we cannot determine what exact value
			//causes the inconsistency, it is assumed the last value caused it
			setPhase(phase-1);
			PRUNE(curVar,curValue);
#ifdef DOMAIN_SPLIT
			setPhase(phase);
			domainSplitting=true;
			consistent=MAC(pruneThese);  //pruning must be done as a current-level function.
			domainSplitting=false;
#else
			consistent=MAC(pruneThese);
			setPhase(phase);
#endif
			//NEW:  if the removal of the current value causes arc-inconsistency, then
			//backtrack and remove the currently assigned value.  If that removal causes
			//inconsistency, backtrack again and remove that value, etc.
			while(!consistent){ 
#ifdef DOMAIN_SPLIT
			domainSplitting=true;
			restoreDomains(phase);
			domainSplitting=false;
			//cout << "Domain Inconsistent Tree at phase " << phase << endl;
#endif

			if(phase==0){
	#ifdef DOMAIN_SPLIT
				if(domainSet[0]>=maxDomSegs[0])
	#endif
				{
					phase=-2;
					satisfiable = false;
					break;
				}
			} 
#ifdef DOMAIN_SPLIT
				if(domainSet[phase]>=maxDomSegs[phase])
#endif
				{
					//cout << "Arc Inconsistent Tree at phase " << phase << endl;
					numOfBacktracks++;
#ifdef EXTENDED_STATISTICS
					backtrack_levels[curPhase]++;
					if(curPhase>deepest_backtrack)
						deepest_backtrack=curPhase;
#endif

					phase--; // backtrack to the previous phase
					restoreDomains(phase); // restore the domains
					RESTORE_MAC(phase); // restore the internal state of MAC4
					restoreBT(phase); // restore the internal state of this BT search.
#ifdef DOMAIN_SPLIT
					curSeg=maxDomSegs[phase]-domainSet[phase];
#endif
					setPhase(phase-1);
					PRUNE(curVar,curValue);
#ifdef DOMAIN_SPLIT
					setPhase(phase);
					domainSplitting=true;
					consistent=MAC(pruneThese);
					domainSplitting=false;
#else
					consistent=MAC(pruneThese);
					setPhase(phase);
#endif
				}
#ifdef DOMAIN_SPLIT
				else
				{
					//cout << "Advancing Domain Segment" << endl;
					//printDomain(curVar);
					consistent=nextSeg();
					//printDomain(curVar);
					domainSplitting=true;
					if(consistent)
						consistent=MAC(curVar);
					domainSplitting=false;
				}
#endif

		}
	  }
//remember this? this is the second half of the IF statement started on line 130.
//It's basically the same code as above, but this is the only place capable of splicing.
#ifdef DOMAIN_SPLIT  
	  }
	  else
	  {
		  //cout << "Failure by segmentation." << endl;
		  consistent=false;
		  while(!consistent){ 
			//cout << "Domain Inconsistent Tree at phase " << phase << endl;
			domainSplitting=true;
			restoreDomains(phase);
			domainSplitting=false;
			if(phase==0 && domainSet[0]>=maxDomSegs[0]){
				phase=-2;
				satisfiable = false;
				break;
			} 
			if(domainSet[phase]>=maxDomSegs[phase])
			{
					//cout << "Arc Inconsistent Tree at phase " << phase << endl;
					numOfBacktracks++;
#ifdef EXTENDED_STATISTICS
					backtrack_levels[curPhase]++;
					if(curPhase>deepest_backtrack)
						deepest_backtrack=curPhase;
#endif

					phase--; // backtrack to the previous phase
					restoreDomains(phase); // restore the domains
					RESTORE_MAC(phase); // restore the internal state of MAC4
					restoreBT(phase); // restore the internal state of this BT search.

					curSeg=maxDomSegs[phase]-domainSet[phase];
					setPhase(phase-1);
					PRUNE(curVar,curValue);
					setPhase(phase);

					domainSplitting=true;
					consistent=MAC(pruneThese);
					domainSplitting=false;
			}
			else
				{
					//cout << "Advancing Domain Segment" << endl;
					//printDomain(curVar);
					consistent=nextSeg();
					//printDomain(curVar);
					domainSplitting=true;
					if(consistent)
						consistent=MAC(curVar);
					domainSplitting=false;
				}

		}
	  }
#endif
	} // end of while loop on all variables
    
    if(phase >= n)
      satisfiable = true; 
  }
	return satisfiable;
} // end of class

#ifdef DOMAIN_SPLIT
bool BT::initSplit()
{
	bool state=domainSplitting;
	domainSplitting=true;
	//cout << "Creating Segments for Variable " << curVar << endl;
	//printDomain(curVar);
		domainSet[phase]=0;
		maxDomSegs[phase]=0;
		curSeg=0;
		Domain *dp=vars[curVar].dp;
		bool consistent=true;
		int vi=d;
		while(consistent && vars[curVar].domainSize>SEG_SIZE)
		{
			//cout << "Segment " <<curSeg << ":";

			//find the next viable domain value.  only important
			//when a previous segmentation caused the removal of
			//the value vi
			while(!dp[vi].yes)
				vi--;
			for(int i=0;i<SEG_SIZE;vi=dp[vi].pre,i++)
			{
				remove(curVar,vi);
			//	cout << vi << " ";
			}
			//cout << endl;
			//cout << "Segment.MAC" << endl;
			consistent=MAC(curVar);
			maxDomSegs[phase]++;
			curSeg++;
		}
		//if(curSeg==0)
		//	cout << "No Segmentation." << endl;
		//else
		//	cout << endl;
		while((!consistent) && curSeg>=0)
		{
			//cout << "Too far, inconsistency created." << endl;
			consistent=nextSeg();
			if(consistent)
				consistent=MAC(curVar);
		}
	domainSplitting=state;
	//cout << "Finished Segmenting, curSeg=" << curSeg << endl;
	//printDomain(curVar);
	return (consistent);
	
}

bool BT::nextSeg()
{
	//cout << "Advancing Segment " << curSeg << " to " << curSeg-1 << endl;
	if(curSeg>0)
	{
		bool state=domainSplitting;
		domainSplitting=false;
		Domain *dp=vars[curVar].dp;
		setPhase(phase-1);
		for(int vi=dp[0].next;vi!=0;vi=dp[vi].next)
		{
			//any values still within the domain at this point are failures.
			remove(curVar,vi);  
			//cout << "removed " << vi << " Due to total segment failure." << endl;
		}
		setPhase(phase);
		domainSplitting=true;
		curSeg--;
		domainSet[phase]++;
		restoreDomains(phase);
		domainSplitting=state;
#ifdef REPERMAT
		if(domainSet[phase]%REPERMAT==0 && maxDomSegs[phase]-domainSet[phase]>NOREPERMAT)
			if(!permMaint())
				curSeg=-1;
#endif
	}
	else
	{
		curSeg--;
		domainSet[phase]++;
	}
	return (curSeg>=0);
}
	

//Unknown whether this works or not.  The idea is to remove all values that do not work
//due to the removal of previous segments.  It's relatively expensive to perform.
//The activation of this function is controlled by REPERMAT and NOREPERMAT. 
//REPERMAT controls how many segments should be cycled before activation.
//NOREPERMAT prevents permMaint from happening within X segments of the final segment.
bool BT::permMaint()
{
	stack<RemovedValue> storage;
	RemovedValue rmVal;
	bool state=domainSplitting;
	bool consistent;
	while(!splitValues.empty())
	{
		rmVal=splitValues.top();
		if(rmVal.phase < phase) break;
		storage.push(rmVal);
		insert(rmVal.var,rmVal.value);
		splitValues.pop();
	}
	domainSplitting=false;
	setPhase(phase-1);
	consistent=MAC(curVar);
	setPhase(phase);
	if(!consistent)
	{
		domainSplitting=state;
		return false;
	}
	while(!storage.empty())
	{
		rmVal=storage.top();
		if(vars[curVar].dp[rmVal.value].yes)
		{
			remove(rmVal.var,rmVal.value);
			splitValues.push(rmVal);
		}
		storage.pop();
	}
	domainSplitting=state;
	return true;
}
#endif

// restore the states of BT before (not including) previousPhase.   
void BT::restoreBT(int previousPhase){
  restoreVars(curVar); // set current var unassigned
  curVar = assignedVars[previousPhase]; // move to the previous variable
  curValue = valueOfVars[curVar];
  restoreVars(curVar);
  adjustDegree(curVar,false);
}

// assign value to var
void BT::assignVar(int var, int value) {

  //cout << "Variable " << curVar << " marked assigned." << endl;                                                                        
  valueOfVars[var] = value;                                                                                
  /* backup is not necessary in simple backtracking
  Assignment assignment;
  assignment.var = var;
  assignment.value = value;
  assignment.phase = curPhase;
  previousAssignments.push(assignment);
  */
}

// restore the assignments of variables
void BT::restoreVars(int varia) {

  //cout << "Variable " << curVar << " marked unassigned." << endl;                                                                                 
  valueOfVars[varia] = -1;// make it unassigned
  /* restore is not necessary in simple backtracking
  Assignment assignment;
  assignment = previousAssignments.top();
  while((*assignment).phase > curPhase) {
    // restore the assignment
    valueOfVars[(*assignment).var] = (*assignment).value;
    previousAssignments.pop();
    assignment = previousAssignments.top();
  }
  */
}

void BT::printSystem()
{
	//cout << "Assigned Variable List: ";
	//for(int i=0;i<n;i++)
	//	if(isAssigned(i))
	//		cout << i << " ";
	cout << endl << "Unassigned Variable List: ";
	for(int i=0;i<n;i++)
		if(!isAssigned(i))
			cout << i << " ";
	cout << endl << "Assigned Variable Order: ";
	for(int i=0;i<curPhase;i++)
		cout << assignedVars[i] << " ";
	cout << endl;
	//cout << endl << "Printing Domain System." << endl;
	//for(int i=0;i<n;i++)
	//	if(!isAssigned(i))
	//		printDomain(i);
}

//this function keeps the current degree calculated. Whenever a variable is assigned, this 
//function should be called with dec=true.  When a variable is unassigned, it must be called
//with dec=false
void BT::adjustDegree(int var, bool dec)
{
	if(dec)
		for(list<int>::iterator iter=cross_link_list[var].begin(); iter!=cross_link_list[var].end(); iter++)
			vars[*iter].degree--;
	else
		for(list<int>::iterator iter=cross_link_list[var].begin(); iter!=cross_link_list[var].end(); iter++)
			vars[*iter].degree++;
}


// the virtual function used for MAC4
bool BT::isAssigned(int i){
  if(valueOfVars[i] == -1) return false;
  else return true;
}

void BT::printSolution(){

  std::cout << "The solution is: xi=value\n";
  for(int i=0; i<n; i++){
    std::cout << 'x' << i << '=' << valueOfVars[i] << ' ';
    if ( (i+1) % 8 == 0) std::cout << '\n';
  }
  std::cout << '\n';
}

#ifdef VAL_COMPUTE
void BT::printValueSelection()
{
	cout << "Variable\tValue\t\tSupports\tConflicts" << endl;
	for(int i=0;i<n;i++)
	{
		cout << i << "\t\t" << valueOfVars[i] 
			 << "\t\t" << valConnect[i*d+valueOfVars[i]-1].size()
			 << "\t\t" << valConflict[i*d+valueOfVars[i]-1].size() << endl;
	}
	getchar();
}
#endif

//Simple function checks whether a given solution is correct.  Useful
//for diagnosing errors.  It will give massive errors if there is no
//solution (does not check for failed system)
void BT::checkSolution()
{
	cout << "Checking Solution Against Constraint Graph" << endl;
	bool failure=false;
	for(int i=0;i<n;i++)
	{
		for(list<int>::iterator iter=cross_link_list[i].begin();iter!=cross_link_list[i].end();iter++)
		{
			if(!validtuple(i,*iter,valueOfVars[i],valueOfVars[*iter]))
			{
				cout << "Failure on Pair (" << i << "," << *iter << ")" << endl;
				failure=true;
			}
		}	
	}
	if(!failure)
		cout << "Solution Acceptable." << endl;
}

int BT::getNumOfBacktracks() {
  return numOfBacktracks;
}

int BT::getMaxSearchDepth() {
  return maxSuccessfulPhase;
}

void BT::statistics() {

  AC_CLASS::statistics();
  std::cout << "[BT::statistics()] #backtracks=" << numOfBacktracks
	    << ' ' << "maxPhase=" << maxSuccessfulPhase << '\n';

  std::cout << "number of failed assignments:" 
	    << numOfFailedAssignments << '\n'; 
  cout << "number of pruned values:" << numPruned << endl;
#ifdef EXTENDED_STATISTICS
  std::cout << "Backtracks by level:\n[";
  for(int i=0;i<n;i++)
	  std::cout << backtrack_levels[i] << ' ';
  std::cout << "]\n";
#endif

}
